package org.example.Soution004;

public class SkillDuplicateNumber {
    public static void main(String[] args) {
        SkillDuplicateNumber obj = new SkillDuplicateNumber();
        int[] nums=new int[]{1,3,4,2,2};
        System.out.println(obj.findDuplicate(nums));
    }

    public int findDuplicate1(int[] nums) {
        int n = nums.length;
        int start=1,end=n-1;
        while(start<end){
            int mid=start+(end-start)/2;
            int count=0;
            for(int i=0;i<n;i++){
                if(nums[i]<=mid){
                    count++;
                }
            }
            if(count>mid){
                end=mid;
            }else{
                start=mid+1;
            }
        }
        return start;
    }

    public int findDuplicate(int[] nums) {
        int fast=nums[0],slow=nums[0];
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while(slow!=fast);

        fast=nums[0];
        while(fast!=slow){
            fast=nums[fast];
            slow=nums[slow];
        }
        return fast;
    }
}
